package warthog.scangen;

import java.io.IOException;
import java.util.*;


public class DNode {
	/**
	 * Involved in the determinization process. Given a set of NDFSM states,
	 * we'd like to return an existing node if possible, otherwise
	 * create a new one and return that. The given set may not be
	 * closed over epsilon, and we don't own it, so we need to make
	 * a copy first, then close the copy, and then run a comparison. 
	 */
	private static Map<Set<Node>, DNode> map = new HashMap<Set<Node>, DNode>();
	public static Collection<DNode> all() { return map.values(); }
	public static DNode fetch(Set<Node> nodes) {
		Set<Node> myCopy = new HashSet<Node>(nodes);
		Node.close(myCopy);
		if (map.containsKey(myCopy)) return map.get(myCopy);
		return new DNode(myCopy);
	}
	/**
	 * DNode construction feeds the determinization process forward
	 * in a depth-first search as it builds out the edge structure.
	 */
	private Rule rule;
	private DNode(Set<Node> subset) {
		// First thing: enter this into the subset-construction dictionary before
		// trying to find successor states, lest graph cycles cause problems.
		map.put(subset, this);
		for (Node n:subset) rule = (null==rule) ? (n.rule) : rule.compete(n.rule);
		if (rule != null) rule.reached=true;
		// Now build the edge map.
		for (Character ch:boundsList(subset)) {
			addEdge(ch, fetch(followSet(subset, ch)));
		}
	}
	private static Set<Node> followSet(Set<Node> subset, Character ch) {
		HashSet<Node> successor = new HashSet<Node>();
		for (Node n:subset) successor.addAll(n.after(ch));
		return successor;
	}
	private static Collection<Character> boundsList(Set<Node> subset) {
		TreeSet<Character> foo = new TreeSet<Character>();
		foo.add((char) 0);
		for (Node n:subset) foo.addAll(n.boundList());
		return foo;
	}
	/**
	 * Now we need a means of working with the edge list.
	 * The structure I propose is a pair of arrayList<Character>
	 * and <DNode>. The character is the lower bound on those leading to DNode.
	 * The error state will show up as a special DNode with an empty subset...
	 */
	private ArrayList<Character> bounds = new ArrayList<Character>();
	private ArrayList<DNode> targets = new ArrayList<DNode>();
	private void addEdge(Character ch, DNode target) {
		// We're counting on these to happen in character code order...
		bounds.add(ch); targets.add(target);
	}
	public boolean isDistinct(DNode that) {
		if (this == that) return false;
		if (this.rule != that.rule) {
			if (null == this.rule || null == that.rule) return true;
			if (! this.rule.action.equals(that.rule.action)) return true;
		}
		return this.partiallyDistinct(that) || that.partiallyDistinct(this);
	}
	private boolean partiallyDistinct(DNode that) {
		for (Character b:bounds) {
			if (this.next(b).color != that.next(b).color) return true;
		}
		return false;
	}
	private DNode next(Character b) {
		return targets.get(indexFor(b));
	}
	private int indexFor(Character goal) {
		int left=0, right=bounds.size();
		// Find the maximal M such that bounds.get(M) <= goal.
		// Must not probe past end of list.
		// So search for the least M where bounds.get(M) > goal,
		// and then return one less than that index.
		while (left<right) {
			int mid = (left+right)/2;
			if (bounds.get(mid) > goal) {
				right=mid; // mid is an upper bound on the correct answer.
			} else {
				left=mid+1; // mid is definitely too small. 
			}
		}
		return left-1;
	}
	Color color;
	void codeBounds(StringBuilder w) throws IOException {
		w.append("\t\t{");
		for (Character ch:bounds) {
			w.append(""+(int)ch.charValue()+",");
		}
		w.append("},\n");
	}
	void codeEdges(StringBuilder w) throws IOException {
		w.append("\t\t{");
		for (DNode d:targets) {
			w.append(""+d.color.index+",");
		}
		w.append("},\n");
	}
	void codeAccept(StringBuilder w) {
		if (rule==null) w.append('0');
		else w.append(Integer.toString(rule.id));
		w.append(",");
	}
}
